Function type - Another Algebraic Data Type

12th鐵人賽 kotlin software development functional programming

hungyanbin

團隊Kotlin 鐵人陣

2020-09-27 00:57:17

824 瀏覽

分享至

在之前的 Algebraic Data Type 中介紹了加法與乘法，也就是 Sum Type and Product Type，今天再來介紹另外一種 Algebraic Data Type - Exponential Type！

怎樣的資料格式會是“指數”的關係呢？其實標題已經爆雷了，就是 function type！其實這比 Sum Type 跟 Product Type 還難理解一點。什麼，連這兩個都忘了嗎？沒關係，先讓我們複習一下 Sum Type 跟 Product Type 吧。

// Sum type：只有 Some 或是 None 兩種 ( T + 1 )
sealed class Maybe<T> {
  class Some(value T): Maybe<T>
  class None(); Maybe<T>
}

// Product type :  first, second 彼此是獨立的互不干擾，可能性為 (T * R)
class Pair<T, R>(val first: T, val second: R)

Maybe<Boolean> => 2 + 1 種可能的值
Pair<Boolean, Byte> => 2 * 256 種可能的值

那 Function Type 的數量怎麼算呢？就用最簡單的方法，窮舉法。

// 紅燈要停還是要走呢？不同地區應該有不同的策略ＸＤ
typealias Walk = (Light) -> Boolean

enum class Light { GREEN, YELLOW, RED}
// 不管是什麼燈，往前衝就對了
val walk1: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> true
        Light.YELLOW -> true
    }
}

val walk2: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> true
        Light.YELLOW -> false
    }
}

val walk3: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> false
        Light.YELLOW -> true
    }
}

val walk4: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> true
        Light.GREEN -> false
        Light.YELLOW -> false
    }
}

val walk5: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> true
        Light.YELLOW -> true
    }
}

val walk6: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> true
        Light.YELLOW -> false
    }
}

val walk7: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> false
        Light.YELLOW -> true
    }
}

val walk8: (Light) -> Boolean = { light ->
    when(light) {
        Light.RED -> false
        Light.GREEN -> false
        Light.YELLOW -> false
    }
}

上面的範例中， Light.RED 有可能為 true 或是 false ，Light.YELLOW 有可能為 true 或是 false ，Light.GREEN 有可能為 true 或是 false ，所以是 2 * 2 * 2 = 8 ，總共 8 種，也可以寫成 2^3 = 8 ，2 對應到的是 Boolean ， 3 對應到的則是 Light，由這個例子中看出了原來 Function Type 是一個“指數”的關係：

function type: (T) -> R
number of possibilities: (number of R) ^ (number of T)

更多的代數

還記得上次的 Algebraic Data Type 轉成數學式的推斷嗎？有了 Exponential Type 我們可以玩更多了！來看看下面這幾種各代表什麼意思：

a ^ 1 = a    //1
1 ^ a = 1    //2

任何數字的 1 次方還是等於本身的數字，還記得 1 可以替換成誰嗎？是 Unit ! ，所以等式的左邊可以替換成： (Unit) → A ，這是什麼函式呢？一個輸入是 Unit 的 function 幾乎等於沒有輸入只有輸出！也就是說可以把它看成 getter() ，所以總共是 A 種可能性，跟等式的右邊一樣。
數字 1 的任何次方，就是等於 1 乘了很多次，那最後的結果當然還是等於 1。接著，等式的左邊 1 ^ a 可以替換成 (A) → Unit ，這又是什麼意思呢？這是一個完全不管輸入的 function ，輸出永遠是 Unit ， fun boo(input: A) = Unit ，所以只有一種可能性，與等式的右邊也相同。

再來看看下一個：

不知道大家有沒有忘了這條公式呢？乘方的乘方等於乘方相乘，那他相對應的 Algegraic Data Type 又會是怎樣呢？

Left: (N) -> (M) -> A
Right: (Pair<N, M>) -> A

竟然出現了兩個箭頭！這是什麼可怕的東西！為了讓左邊看起來不這麼可怕，把第一個箭頭轉換成我們熟悉的 kotlin function 吧！把 N 當成輸入， (M) → A 當成輸出

fun left(n: N): (M) -> A { ... }

Left 變成了我們比較熟悉的 Higher order function 了，返回值是一個 function type ，恩...？等等，在兩天前好像看過類似的結構不是嗎？ left 的返回類型可以轉為 Reader Monad ！

fun left(n: N): Reader<M, A> = { ... }

再來看看右邊，一樣先把他轉為我們熟悉的 kotlin function

fun right(pair: Pair<N, M>): A { ...}

一個輸入為 Pair 的參數其實有點冗余，他其實可以拆開來變成兩個參數：

fun right(n: N, m: M): A {...}
// 一起拿來比較
fun left(n: N): Reader<M, A> = { ... }

這不就是跟兩天前的內容一模一樣嗎？不過是對象 M 換成 GithubRepository 罷了！更好玩的是，如果再轉換回函數型別，就會意外得到柯里化（之後將會介紹）的轉換公式：

left = (Pair<N, M>) -> A = (N, M) -> A 
right = (N) -> (M) -> A 

(N, M) -> A = (N) -> (M) -> A

小結

今天介紹了 function type 作為 Algebraic Data Type 的樣子，不知道你是否也覺得很有趣呢？其實任何一個 Algebraic Data Type 本身都可以形成一個 Functor ，就如同今天提到的 Reader 是 Exponential Type， Maybe 是 Sum Type，還有一些不會介紹到的容器例如： State - [ (S) → (S, A) ] 是 Exponential Type 跟 Product Type 的綜合體。至於為什麼他們一定都是 Functor 呢？恩...請原諒我現在還沒有能力證明他們，如果對這相關的證明有興趣的話，可以觀看以下這一系列影片：

https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_

大概看到 6.2 就會證明給你看了，祝大家觀看愉快！